﻿package code {
	import flash.geom.Rectangle;
	public class QuadTree {
		public var rect:Rectangle;
		public var divisions:Array;
		public var collisionObjects:Array;
		
		public const MAX_OBJECTS_BEFORE_SUBDIVIDE:int = 300;
		public var subdivided:Boolean;
		public function QuadTree(xPos:int, yPos:int, widthObj:int, heightObj:int) {
			rect = new Rectangle(xPos, yPos, widthObj, heightObj);
			divisions = new Array();
			collisionObjects = new Array();
			subdivided = false;
		}
		
		// adds an object to the quadtree
		public function addObject(lineToAdd:Line){
			var toDivided:Boolean = false;
			
			// if the line will fit in one of the divisions of the rectangle, it will go all the way through and check
			if(lineInRect(lineToAdd, rect)){
				if(divisions != null){
				   for(var i:int = 0; i < divisions.length; i++){
					   if(lineInRect(lineToAdd, rect)){
						   divisions[i].addObject(lineToAdd);
						   
						   toDivided = true;
					   }
				   }
				}
			}
			
			// if there are no divisions, it simply adds the line to this array
			if(toDivided == false){
				collisionObjects.push(lineToAdd);
			}
			
			if(collisionObjects.length > MAX_OBJECTS_BEFORE_SUBDIVIDE && subdivided == false){
				divide();
				subdivided = true;
			}
		}
		
		public function divide(){
			divisions = new Array(4);
			divisions[0] = new QuadTree(rect.x, rect.y, rect.width / 2, rect.height / 2);
			divisions[1] = new QuadTree(rect.x + (rect.width / 2), rect.y, rect.width / 2, rect.height / 2);
			divisions[2] = new QuadTree(rect.x, rect.y + (rect.height / 2), rect.width / 2, rect.height / 2);
			divisions[3] = new QuadTree(rect.x + (rect.width /2), rect.y + (rect.height / 2), rect.width / 2, rect.height / 2);
			
			var index:Array = new Array();
			
			// divides up the collision objects into the proper child quadtrees
			for(var i:int = 0; i < collisionObjects.length; i++){
				for(var j:int = 0; j < divisions.length; j++){
					if(lineInRect(collisionObjects[i], divisions[j].rect)){
						divisions[j].addObject(collisionObjects[i]);
						index.push(i);
					}
				}
			}
			
			for(var k:int = 0; k < index.length; k++){
				collisionObjects.splice(index[i] - i);
			}
			
			trace("Current quad length after division: " + collisionObjects.length);
		}
		
		public function getContainingQuad(ball:Ball):QuadTree{
			if(!(ballInRect(ball, rect))){
				return null;
			}
			else{
				if(divisions != null){
					for(var i:int = 0; i < divisions.length; i++){
						var quad:QuadTree;
						if((quad = divisions[i].getContainingQuad(ball)) != null){
							return quad;
						}
					}
				}
				return this;
			}
		}
		
		public function collide(quad:QuadTree, quadTreeArray:Array):Array{
			quadTreeArray.push(this);
			if(quad != null && rectInRect(quad.rect, rect)){
				if(divisions != null){
					for(var i:int = 0; i < divisions.length; i++){
						divisions[i].collide(quad, quadTreeArray);
					}
				}
			}
			return quadTreeArray;
		}
		
		public function getContainingQuadLine(lineToCheck:Line):QuadTree{
			if(!(lineInRect(lineToCheck, rect))){
			   return null;
			}
			else{
				if(divisions != null){
					for(var i:int = 0; i < divisions.length; i++){
						var quad:QuadTree;
						if((quad = divisions[i].getContainingQuadLine(lineToCheck)) != null){
							return quad;
						}
					}
				}
				return this;
			}
		}
		
		// helper methods
		public function lineInRect(lineToCheck:Line, rectToCheck:Rectangle):Boolean{
			
			var a:Vertex = lineToCheck.a;
			var b:Vertex = lineToCheck.b;
			
			// if the line is inside the current quad tree
			if(a.x >= rectToCheck.x && a.x <= (rectToCheck.x + rectToCheck.width) && a.y >= rectToCheck.y && a.y <= (rectToCheck.y + rectToCheck.height) && 
			   b.x >= rectToCheck.x && b.x <= (rectToCheck.x + rectToCheck.width) && b.y >= rect.y && b.y <= (rectToCheck.y + rectToCheck.height)){
				return true;
			}
			return false;
		}
		
		public function ballInRect(ballToCheck:Ball, rectToCheck:Rectangle):Boolean{
			var a:Vertex = new Vertex(ballToCheck.x, ballToCheck.y);
			if(a.x >= rectToCheck.x && a.x <= (rectToCheck.x + rectToCheck.width) && a.y >= rectToCheck.y && a.y <= (rectToCheck.y + rectToCheck.height)){
				return true;
			}
			return false;
		}
		
		public function rectInRect(rectToCheck:Rectangle, otherRect:Rectangle):Boolean{
			if(rectToCheck.left >= otherRect.left && rectToCheck.right <= otherRect.right && rectToCheck.top >= otherRect.top && rectToCheck.bottom <= otherRect.bottom){
				return true;
			}
			return false;
		}
		
		// deletes specified line from array
		public function deleteObject(lineToRemove:Line):QuadTree{
			for(var i:int = 0; i < collisionObjects.length; i++){
				if(collisionObjects[i].a == lineToRemove.a && collisionObjects[i].b == lineToRemove.b){
					trace("Line deleting: " + collisionObjects[i].a.x, collisionObjects[i].a.y, collisionObjects[i].b.x, collisionObjects[i].b.y);
					collisionObjects.splice(i, 1);
					i--;
				}
			}
			return this;
		}

	}
	
}
